package com.lili.divide;

/**
 * @Auther: 李 力
 * @Date: 2024/8/20
 * @Description: x 的平方根
 * @version: 1.0
 */
public class LeetCode69 {
    /*
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     * */
    public static int mySqrt(int n) {
        int i = 1;
        int j = n;
        int r = 0;
        while (i <= j) {
            int m = (i + j) >>> 2;
            int mm = m * m;
            if (mm <= n/m) {
                i = m + 1;
                r = m;
            } else {
                j = m - 1;
            }
        }
        return r;
    }
}
